import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-10-14
 * Time:15:24
 */

//反转一个单链表。
//class Solution {
//    public ListNode reverseList(ListNode head) {
//        if(head==null||head.next==null){
//            return head;
//        }
//        ListNode cur =head.next;
//        head.next=null;
//        while (cur!=null){
//            ListNode ret=cur.next;
//            cur.next=head;
//            head=cur;
//            cur=ret;
//        }
//        return head;
//    }
//}


    //给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
    //第一种遍历两次
//class Solution {
//    public ListNode middleNode(ListNode head) {
//        ListNode cur=head;
//        int size=0;
//        hile (cur!=null){
////            cur=cur.next;
////            size++;
////        }w
//        cur=head;
//        for (int i = 0; i < size/2; i++) {
//            cur=cur.next;
//        }
//        return cur;
//    }
//}
//只遍历一次
//class Solution {
//    public ListNode middleNode(ListNode head) {
//        ListNode fast=head;
//        ListNode slow=head;
//        while (fast!=null&&fast.next!=null){
//            slow=slow.next;
//            fast=fast.next.next;
//        }
//        return slow;
//}


    //输入一个链表，输出该链表中倒数第k个结点。
//遍历两次
//class Solution {
//    public ListNode FindKthToTail(ListNode head,int k) {
//        if(head==null){
//            return head;
//        }
//        ListNode cur=head;
//        int size=0;
//        while (cur!=null){
//            cur=cur.next;
//            size++;
//        }
//        if(k>size){
//            return null;
//        }
//        cur=head;
//        for(int i=0;i<size-k;i++){
//            cur=cur.next;
//        }
//        return cur;
//    }
//}


    //遍历一次
//class Solution{
//    public ListNode FindKthToTail(ListNode head,int k) {
//        if(k<=0|| head==null){
//            //返回null;
//            return head;
//        }
//        ListNode fast=head;
//        ListNode slow=head;
//        for (int i = 0; i < k-1; i++) {
//            fast=fast.next;
//            if(fast==null){
//                return null;
//            }
//        }
//        while(fast!=null){
//            fast=fast.next;
//            slow=slow.next;
//        }
//        return slow;
//    }
//    if(k<=0|| head==null){
//        return null;
//    }
//    ListNode fast=head;
//    ListNode slow=head;
//    // while(k-1!=0){
//    //     fast=fast.next;
//    //     if(fast==null){
//    //         return null;
//    //     }
//    //     k--;
//    // }
//        for (int i = 0; i <k-1; i++) {
//        fast=fast.next;
//        if(fast==null){
//            return null;
//        }
//    }
//        while(fast.next!=null){
//        fast=fast.next;
//        slow=slow.next;
//    }
//        return slow;
//}


class Solution {
//    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        if(list1==null){
//            return list2;
//        }
//        if(list2==null){
//            return list1;
//        }
//        ListNode list;
//        ListNode cur1=list1;
//        ListNode cur2=list2;
//        if(cur1.val<cur2.val) {
//            list=cur1;
//            cur1=cur1.next;
//        }else {
//            list=cur2;
//            cur2=cur2.next;
//        }
//        ListNode cur=list;
//        while(cur1!=null&&cur2!=null){
//            if(cur1.val<cur2.val){
//                //添加
//                cur.next=cur1;
//                cur1=cur1.next;
//                cur=cur.next;
//            }else{
//                cur.next=cur2;
//                cur2=cur2.next;
//                cur=cur.next;
//            }
//        }
//        while(cur1!=null){
//            cur.next=cur1;
//            cur1=cur1.next;
//            cur=cur.next;
//        }
//
//        while(cur2!=null){
//            cur.next=cur2;
//            cur2=cur2.next;
//            cur=cur.next;
//        }
//        return list;
//    }


    //优化：
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        if(list1==null){
//            return list2;
//        }
//        if(list2==null){
//            return list1;
//        }

//        if(cur1.val<cur2.val) {
//            list=cur1;
//            cur1=cur1.next;
//        }else {
//            list=cur2;
//            cur2=cur2.next;
//        }
        ListNode list=new ListNode(-1);
        ListNode cur1=list1;
        ListNode cur2=list2;
        ListNode cur=list;
        while(cur1!=null&&cur2!=null){
            if(cur1.val<cur2.val){
                //添加
                cur.next=cur1;
                cur1=cur1.next;
                cur=cur.next;
            }else{
                cur.next=cur2;
                cur2=cur2.next;
                cur=cur.next;
            }
        }
        while(cur1!=null){
            cur.next=cur1;
            cur1=cur1.next;
            cur=cur.next;
        }

        while(cur2!=null){
            cur.next=cur2;
            cur2=cur2.next;
            cur=cur.next;
        }
        return list.next;
    }

}

public class Test {
    public static void main(String[] args) {
        ListNode listNode1=new ListNode(-9);
        ListNode listNode2=new ListNode(3);
        listNode1.next=listNode2;
        ListNode listNode3=new ListNode(5);
        ListNode listNode4=new ListNode(7);
        listNode3.next=listNode4;
        ListNode listNode=Solution.mergeTwoLists(listNode1,listNode3);
        System.out.println(listNode);
    }
}
